#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

void print_array(char* str,int* a,int len){
	int i;
	for(i=0;i<len;i++){
		if(str!=NULL)
			printf("%d,%s ",a[i],str+a[i]);
		else
			printf("%d ",a[i]);
	}
	printf("\n");
}

int kmp(char* a,char* b){
	int lenb=strlen(b);
	
	int* t=malloc(sizeof(int)*lenb);
	int i=0;
	char* pa=a,*pb=b;
	while(*pa!=0 && *pb!=0){
		//printf("%c,%c %d,%d\n",*pa,*pb,i,t[i]);
		if(*pa==*pb){
			if(i==0){
				t[i]=0;
				i++;
			}else if(*pa==*(b+t[i-1])){
				t[i]=t[i-1]+1;
				i++;
			}else{
				t[i]=0;
				i++;
			}
			pa++;pb++;
		}else{
			//pa-=t[i-1]+1;
			if(i==0){
				pa++;
				pb=b;
				i=0;
			}else{
				pb=b+t[i-1];
				i=t[i-1];
			}
		}
		if(*pb==0)
			return pa-lenb-a;
	}
	return -1;
}
void aswap(int* a,int i,int j){
	int tmp=a[i];
	a[i]=a[j];
	a[j]=tmp;
}

int acmp(char* a,char* b){
	//int r=strcmp(a,b);
	int r=0;

	int i;
	int lena=strlen(a);
	int lenb=strlen(b);
	for(i=0;i<lena && i<lenb;i++){
		//printf("%c %c %d\n",a[i],b[i],a[i]-b[i]);
		if(a[i] < b[i]){
			//return -1;
			r=-1;
			break;
		}else if(a[i] > b[i]){
			//return 1;
			r=1;
			break;
		}
	}
	if(r==0)
		r=lena-lenb;
	//printf("cmp %s,%s = %d\n",a,b,r);
	return r;
}

void aqsort(char* a,int* ret,int l,int h){
	assert(a!=NULL && ret!=NULL && h!=l);
	printf("process %s %d,%d \n",a,l,h);
	print_array(a,ret,11);
	int i=l+1,j=h;
	if(i==j){
		if(acmp(a+ret[l],a+ret[h])>0){
			aswap(ret,l,h);
			return;
		}
		return;
	}
	while(i!=j){
		int last=i;
		while(acmp(a+ret[l],a+ret[i])>0 && i!=j){
			i++;
		}
		while(acmp(a+ret[j],a+ret[l])>0 && j!=i){
			j--;
		}
		if(i==j)
			break;
		aswap(ret,i,j);
		if(i==j-1)
			break;
		i++;
		j--;
	}
	if(acmp(a+ret[l],a+ret[i])<0)
		i--;
	aswap(ret,l,i);		
	printf("%s %d,%d %i\n",a,l,h,i);
	print_array(a,ret,11);
	
	if(i-1>l)
		aqsort(a,ret,l,i-1);
	if(i+1<h)
		aqsort(a,ret,i+1,h);
}



int* suffix_array(char* a){
	int len=strlen(a);
	int* ret=(int*)malloc(sizeof(int)*len);
	int i;
	for(i=0;i<len;i++)ret[i]=i;
	
	aqsort(a,ret,0,len-1);
	return ret;
}

int array_equal(int* a,int *b,int len){
	while(len>0){
		if(a[len-1]!=b[len-1])
			return -1;
		len--;
	}
	return 0;
}


int main(){
	char* a="ABC ABCDAB ABCDABCDABDE";
	char* b="ABCDABD";
	
	char* c="AAAAAAAAAAAAAAAAABAAAAA";
	char* d="AAAAAB";
	//15
	//assert(kmp(a,b)==15);
	printf("%d\n",kmp(a,b));
	assert(kmp(a,b)==strstr(a,b)-a);
	printf("===========================\n");
	printf("%d\n",kmp(c,d));
	assert(kmp(c,d)==strstr(c,d)-c);
	//printf("occor at :%d",strstr(a,b)-a);
	
	char* ss="abracadabra";
	//char* ss="cdefgabnm";
	char* sa=(char*)malloc(strlen(ss)+1);
	strcpy(sa,ss);
	sa[strlen(ss)]=0;
	
	int* ret=suffix_array(sa);
	int sas[]={11,8,1,4,6,9,2,5,7,10,3,0};
	//assert(array_equal(ret,sas,11)==0);
	int i;
	for(i=0;i<11;i++){
		printf("%d %s\n",ret[i],sa+ret[i]);
	}
	
//	assert(acmp())
	
	//printf("%x %s\n",sa,sa);
	//aqsort(sa,sas,0,strlen(sa)-1);
	//printf("%s\n",sa);
	//print_array(sas,11);
}
